package com.suanfa;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class ShuZu
{
    /*
     * 给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。
     * 给定一个数，判断这个数是否在该二维数组中。
     *
     * */
//    public boolean Find(int target, int[][] matrix)
//    {
//        /*
//        [1,   4,  7, 11, 15],
//        [2,   5,  8, 12, 19],
//        [3,   6,  9, 16, 22],
//        [10, 13, 14, 17, 24],
//        [18, 21, 23, 26, 30]
//        * */
//    }


    /*
     *给定一个数组 A[0, 1,..., n-1]，请构建一个数组 B[0, 1,..., n-1]，
     *其中 B 中的元素 B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。要求不能使用除法。
     * （注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）
     * */

    public static int[] multiply(int[] A)
    {
        /*[1,2,3,4,5]       [120,60,40,30,24]
        C[0] = 1
        C[1] = A[0]
        C[2] = A[0] * A[1]
        C[3] = A[0] * A[1] * A[2]

        D[n - 1] = 1
        D[n - 2] = A[n -1]
        D[n - 3] = A[n - 1] * A[n - 2]
        B[i]=C[i]*D[i], C[i]= C[i-1] * A[i-1](i>=1), D[i] = D[i+1]* A[i+1](i<=n-2)
        */
        int length = A.length;
        int[] B = new int[length];
        if (length != 0)
        {
            B[0] = 1;
            //计算下三角C[i]
            for (int i = 1; i <= length - 1; i++)
            {
                B[i] = B[i - 1] * A[i - 1];
            }
            int tempD = 1;//length-1位置上的值
            //计算上三角D[i]
            for (int i = length - 2; i >= 0; i--)
            {
                tempD = tempD * A[i + 1];//D[i]=D[i+1]*A[i+1]
                B[i] = B[i] * tempD;   //B=C*D
            }
        }

        return B;

    }

    /*
     *输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。
     * 求所有子数组的和的最大值。要求时间复杂度为 O(n).
     * */

    public static int findMaxSubArray(int[] array)
    {
        //[1,-2,3,10,-4,7,2,-5], 和最大的子数组为[3,10,一4,7,2], 所以值为18
        int max = array[0];
        int sum = 0;
        for (int i = 0; i < array.length; i++)
        {
            sum = sum + array[i];
            if (sum >= max) max = sum;
            if (sum < 0) sum = 0;
        }
        return max;

    }

    /*
    *把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
     输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
     NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
    *
    * */

    public static int minNumberInRotateArray(int[] array)
    {
        //[3,3,3,1,2]
        //[3,4,5,1,2]
        //[4,5,1,2,3]
        //[5,1,2,3,4]
        int first = 0;
        int last = array.length - 1;   //array[first]为对比目标
        int mid = (first + last) >> 1;
        if (array.length == 0) return 0;
        while (first < last)
        {
            if (array[first] < array[last])
            {
                return array[first];   //提前退出
            }
            else if (array[first] < array[mid])
            {
                first = mid + 1;
            }
            else if (array[mid] < array[last])
            {
                last = mid;
            }
            else first++;        //避免1101111等情况

        }
        return array[first];
    }


    /*
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
     * 由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
     *
     * */

    public static int MoreThanHalfNum_Solution(int[] array)
    {
        //[1,2,3,2,2,2,5,4,2]     2
        int len = array.length / 2;
        //int count=0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++)
        {
            if (map.containsKey(array[i]))
            {
                int c = map.get(array[i]);
                map.put(array[i], c + 1);
            }
            else
            {
                map.put(array[i], 1);
            }

        }

        for (Integer in : map.keySet())
        {
            int i = map.get(in);
            if (i > len) return in;
        }
        return 0;
    }


    /*
     * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。
     * 数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。
     * 请找出数组中任意一个重复的数字。
     * [2, 3, 1, 0, 2, 5]     2
     * */

    public static boolean duplicate(int[] nums, int length, int[] duplication)
    {
        if (nums == null || length <= 0) return false;

        for (int i = 0; i < length; i++)
        {
            //将值为 i 的元素调整到第 i 个位置上
            while (nums[i] != i)
            {
                //i和i位置相同，则表示数字重复
                if (nums[i] == nums[nums[i]])
                {
                    duplication[0] = nums[i];
                    return true;
                }
                swap(nums, i, nums[i]);

            }

        }
        return false;

    }

    private static void swap(int[] nums, int i, int j)
    {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }


    //一个整型数组里除了两个数字之外，其他的数字都出现了两次，找出这两个只出现了一次的数。
    //2,3,3,4,2,1
    public static void FindNumsAppearOnce(int[] array, int num1[], int num2[])
    {
        if (array.length < 2)
        {
            return;
        }
        ArrayList<Integer> list = new ArrayList();
        for (int i = 0; i < array.length; i++)
        {
            if (list.contains(array[i]))
            {
                //删除时需要注意一下，如果直接传入当前数作为参数，它会按照下标进行删除，不会按照对象进行删除，可能会出现越界。
                list.remove(new Integer(array[i]));
            }
            else
            {
                list.add(array[i]);
            }
        }
        num1[0] = list.get(0);
        num2[0] = list.get(1);
    }


}
